#include <iostream>

#define MAXSIZE 100    //顺序查找表的最大长度
typedef int KeyType; //整型关键字类型
typedef int InfoType;

typedef struct {
    KeyType key; //关键字域
    InfoType otherinfo; // 其它数据项
} ElemType; //记录类型

typedef struct {
    ElemType *elem; //记录存储空间基地址，构造表时按实际长度分配，0号单元留空
    int length; //表长度
} SSTable; //静态查找表类型

int Search(SSTable ST, KeyType key) {
    int i;
    for (i = 1; i <= ST.length; i++) {
        if (ST.elem[i].key == key) {
            return i;
        }
    }
    return 0;
}

int Search_Seq(SSTable ST, KeyType key) {
    int i;
    ST.elem[0].key = key;
    for (i = ST.length; ST.elem[i].key != key; i--);
    return i;
}

int Partition(SSTable ST, int low, int high) {
    // 快速排序
    ST.elem[0] = ST.elem[low];
    KeyType pivotkey = ST.elem[low].key;
    while (low < high) {
        while (low < high && ST.elem[high].key >= pivotkey) {
            high--;
        }
        if (low < high) {
            ST.elem[low++] = ST.elem[high];
        }
        while (low < high && ST.elem[low].key <= pivotkey) low++;
        if (low < high) ST.elem[high--] = ST.elem[low];
    }
    ST.elem[low] = ST.elem[0];
    return low;
}

void QuickSort(SSTable &ST, int low, int high) {
    if (low < high) {
        int pivotloc = Partition(ST, low, high);
        QuickSort(ST, low, pivotloc - 1);  // 递归排序左子表
        QuickSort(ST, pivotloc + 1, high); // 递归排序右子表
    }
}

// 打印表内容
void PrintTable(SSTable ST) {
    std::cout << "Current table:\n";
    std::cout << "Position\tKey\tOtherInfo\n";
    for (int i = 1; i <= ST.length; i++) {
        std::cout << i << "\t\t" << ST.elem[i].key << "\t" << ST.elem[i].otherinfo << "\n";
    }
    std::cout << "\n";
}

int Search_Bin(SSTable ST, KeyType key) {
    int low = 1;
    int high = ST.length;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (key == ST.elem[mid].key) return mid;
        else if (key < ST.elem[mid].key) high = mid - 1;
        else low = mid + 1;
    }
    return 0;
}

int main() {
    // 创建并初始化SSTable
    SSTable table;
    table.elem = new ElemType[MAXSIZE + 1]; // 分配空间，0号单元留空
    table.length = 10; // 假设表中有10个元素

    // 填充测试数据
    for (int i = 1; i <= table.length; i++) {
        table.elem[i].key = i * 2; // 关键字为2,4,6,...,20
        table.elem[i].otherinfo = i * 100; // 其他信息为100,200,...,1000
    }

    // 测试Search函数
    std::cout << "Testing Search function:\n";
    KeyType testKeys[] = {4, 7, 10, 20, 25};
    for (int i = 0; i < 5; i++) {
        int pos = Search(table, testKeys[i]);
        if (pos != 0) {
            std::cout << "Key " << testKeys[i] << " found at position " << pos
                      << ", otherinfo: " << table.elem[pos].otherinfo << "\n";
        } else {
            std::cout << "Key " << testKeys[i] << " not found\n";
        }
    }

    // 测试Search_Seq函数
    std::cout << "\nTesting Search_Seq function:\n";
    for (int i = 0; i < 5; i++) {
        int pos = Search_Seq(table, testKeys[i]);
        if (pos != 0) {
            std::cout << "Key " << testKeys[i] << " found at position " << pos
                      << ", otherinfo: " << table.elem[pos].otherinfo << "\n";
        } else {
            std::cout << "Key " << testKeys[i] << " not found\n";
        }
    }

    table.length = 10; // 假设表中有10个元素

    // 填充测试数据（故意打乱顺序）
    table.elem[1].key = 12; table.elem[1].otherinfo = 600;
    table.elem[2].key = 4;  table.elem[2].otherinfo = 200;
    table.elem[3].key = 18; table.elem[3].otherinfo = 900;
    table.elem[4].key = 6;  table.elem[4].otherinfo = 300;
    table.elem[5].key = 10; table.elem[5].otherinfo = 500;
    table.elem[6].key = 2;  table.elem[6].otherinfo = 100;
    table.elem[7].key = 16; table.elem[7].otherinfo = 800;
    table.elem[8].key = 8;  table.elem[8].otherinfo = 400;
    table.elem[9].key = 14; table.elem[9].otherinfo = 700;
    table.elem[10].key = 20; table.elem[10].otherinfo = 1000;


    QuickSort(table, 1, 10);
    PrintTable(table);

    // 测试二分查找
    std::cout << "Testing Search_Bin (Binary Search):\n";

    int pos = Search_Bin(table, 8);
    std::cout << "Key " << 8 << " found at position " << pos
                      << ", otherinfo: " << table.elem[pos].otherinfo << "\n";


    return 0;
}
